package leetcode_1000;

/**
 *@author 周杨
 *SuperPalindromes_906 如果一个数是回文数 且其开方也是回文数 那么这个数是超级回文数 问一个范围内有多少超级回文数
 *describe:常规遍历 AC 74%
 *2018年11月14日 下午7:45:18
 */
public class SuperPalindromes_906 {
	int res = 0;
    int[] nums = new int[50];                    //存储一个字符串的各个位数
    
    public int superpalindromesInRange(String L, String R) {
        long l = Long.parseLong(L);
        long r = Long.parseLong(R);
        
        long lSqrt = (long) Math.sqrt(l);
        long rSqrt = (long) Math.sqrt(r);
        
        int lLen = Long.toString(lSqrt).length();
        int rLen = Long.toString(rSqrt).length();
        
        for(int i = lLen; i <= rLen; i++){
            search(l, r, 0, i-1, i);
        }
        return res;
        
    }
    
    public void search(long low, long hight, int from, int to, int len){
        
        if(from > to){
            long val = 0;
            for(int i = 0; i < len; i++){
                val = val * 10 + nums[i];
            }
            val = val * val;
            if(val >= low && val <= hight && isPalindrome(val)){
                res ++;
            }
        }else{
            int start = 0;
            if(from == 0){
                start = 1;
            }
            for(int i = start; i < 10; i++){
                nums[from] = nums[to] = i;
                search(low, hight, from + 1, to - 1, len);
            }
        }
    } 
    
    public boolean isPalindrome(long val){
        String str = Long.toString(val);
        int l = 0;
        int r = str.length()-1;
        while(l < r && str.charAt(l) == str.charAt(r)){
            l++;
            r--;
        }
        return l >= r;
    }
}
